
//3152.特殊数组II
class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        //此题是对子数组进行判断,判断子数组是否满足特殊数组的条件
        //如果直接暴力求解,O(N^2)超时,需要进行优化
        //可以统计到达每个位置是该位置可以与前面组成的特殊数组的长度;
        //这样在检查一个区间[start,end]的时候,直接检查(end位置组成的特殊数组的长度-start位置组成的特殊数组的长度)是否等于(end-start)即可

        int n = nums.size(),m = queries.size();
        vector<int> lsum(n);
        lsum[0] = 1;
        for(int i = 1; i < n;i++)
        {
            int clo = nums[i]%2 + nums[i-1]%2;       //判断是时不时奇偶相邻,如果是clo为1
            if(clo==1) lsum[i] = lsum[i-1] + 1;      //紧接着上一个继续计数
            else lsum[i] = 1;                        //重新开始计数
        }
        vector<bool> ret(m);
        for(int i = 0 ;i < m; i++)
        {
            int start = queries[i][0],end = queries[i][1];
            ret[i] = (end-start == lsum[end] - lsum[start]);    //判断子数组中间部分奇偶是不是连续的
        }
        return ret;
    }
};